package leetcode.code0910;

import java.util.Arrays;

import leetcode.helper.H;

public class Solution {
	// 11%
	public int smallestRangeII1(int[] nums, int k) {
		Arrays.sort(nums);
		int len = nums.length;
		int L = nums[0] + k, R = nums[len - 1] - k;
		int ans = nums[len - 1] - nums[0];
		for (int i = 1; i < len; i++) {
			int l = nums[i - 1] + k;
			int r = nums[i] - k;
			int max = Math.max(Math.max(L, R), Math.max(l, r));
			int min = Math.min(Math.min(L, R), Math.min(l, r));
			int cur = max - min;
			ans = Math.min(ans, cur);
		}
		return ans;
	}

	// 快2ms 11%
	public int smallestRangeII3(int[] nums, int k) {
		Arrays.sort(nums);
		int len = nums.length;
		int L = nums[0] + k, R = nums[len - 1] - k;
		int ans = nums[len - 1] - nums[0];
		for (int i = 1; i < len; i++) {
			int l = nums[i - 1] + k;
			int r = nums[i] - k;
			int max = Math.max(R, Math.max(l, r));
			int min = Math.min(L, Math.min(l, r));
			int cur = max - min;
			ans = Math.min(ans, cur);
		}
		return ans;
	}

	// 又快 2ms 95.81
	public int smallestRangeII(int[] nums, int k) {
		Arrays.sort(nums);
		int len = nums.length;
		int l = nums[0] + k, R = nums[len - 1] - k;
		int ans = nums[len - 1] - nums[0];
		for (int i = 1; i < len; i++) {
			int r = nums[i - 1] + k;
			int L = nums[i] - k;
			int cur = Math.max(R, r) - Math.min(L, l);
			ans = Math.min(ans, cur);
		}
		return ans;
	}


	public static void main(String[] args) {
		Solution so = new Solution();
		so.smallestRangeII(H.str2array3("[1,2,8,10,11,12]"), 8);
	}
}
